﻿using Microsoft.AspNetCore.Mvc;

namespace LeetCode.API.Controllers
{
    [Route("api/[controller]/[action]")]
    [ApiController]
    public class BaseSortController : ControllerBase
    {
        /// <summary>
        /// 冒泡排序
        /// 依次比较相邻的两个元素，如果前面的数据大于后面的数据，就将两个数据进行交换
        /// 测试用例：4 3 2 1
        /// i = 0; 
        /// j = 1; 3 4 2 1
        /// j = 2; 3 2 4 1
        /// j = 3; 3 2 1 4
        /// 
        /// i = 1;
        /// j = 1; 2 3 1 4
        /// j = 2; 2 1 3 4
        /// 
        /// i = 2;
        /// j = 1; 1 2 3 4
        /// </summary>
        /// <param name="arr"></param>
        [HttpPost]
        public string BubbleSort(int[] arr)
        {
            int count = arr.Length;
            Console.WriteLine("原始数据:" + string.Join(",", arr));
            for (int i = 0; i < count - 1; i++)
            {
                Console.WriteLine($"第{i + 1}次循环开始");
                for (int j = 1; j < count - i; j++)
                {
                    if (arr[j] < arr[j - 1])
                    {
                        Swap(ref arr[j - 1], ref arr[j]);
                    }
                }
                Console.WriteLine("排序结果:" + string.Join(",", arr));
                Console.WriteLine($"第{i + 1}次循环结束");
            }
            Console.WriteLine(string.Format("最终排序结果:{0}", string.Join(",", arr)));
            if (count > 0)
            {
                return string.Join(",", arr);
            }
            return string.Empty;
        }

        /// <summary>
        /// 选择排序
        /// 在要排序的一组数中，选出最小的一个数与第i个位置的数交换，之后依次类推(i=0,1,2,3...)
        /// 测试用例：49 38 65 32
        /// i = 0，min = 3, 32 38 65 49
        /// i = 1, min = 1, 32 38 65 49
        /// i = 2, min = 3, 32 38 49 65
        /// </summary>
        /// <param name="arr"></param>
        /// <returns></returns>
        [HttpPost]
        public string SelectSort(int[] arr)
        {
            int count = arr.Length;
            Console.WriteLine("原始数据:" + string.Join(",", arr));
            for (int i = 0; i < count - 1; i++)
            {
                Console.WriteLine($"第{i + 1}次循环开始");
                int min = i;
                for (int j = i + 1; j < count; j++)
                {
                    if (arr[j] < arr[min])
                    {
                        min = j;
                    }
                }
                //当在此次遍历中，如果没有比arr[i]更小的值，则不用交换
                if (min != i)
                {
                    Swap(ref arr[i], ref arr[min]);
                }
                Console.WriteLine("排序结果:" + string.Join(",", arr));
                Console.WriteLine($"第{i + 1}次循环结束");
            }
            Console.WriteLine(string.Format("最终排序结果:{0}", string.Join(",", arr)));
            return string.Join(",", arr); ;
        }

        /// <summary>
        /// 插入排序
        /// 将原来的无序数列看成含有一个元素的有序序列和一个无序序列，将无序序列中的值依次插入到有序序列中，完成排序
        /// 测试用例： 49 38 65 32
        /// i = 1, j = 0; a[0] > a[1] YES 交换 38 49 65 32
        /// i = 2, j = 1; a[1] > a[2] NO 不交换
        /// i = 2, j = 0; a[0] > a[1] NO 不交换
        /// i = 3, j = 2; a[2] > a[3] YES 交换 38 49 32 65
        /// i = 3, j = 1; a[1] > a[2] YES 交换 38 32 49 65
        /// i = 3, j = 0; a[0] > a[1] YES 交换 32 38 49 65
        /// </summary>
        /// <param name="arr"></param>
        /// <returns></returns>
        [HttpPost]
        public string InsertSort(int[] arr)
        {
            int count = arr.Length;
            Console.WriteLine("原始数据:" + string.Join(",", arr));
            //将a[0]作为有序序列，从索引1开始遍历无序序列
            for (int i = 1; i < count; i++)
            {
                Console.WriteLine($"第{i}次循环开始");
                for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--)
                {
                    Swap(ref arr[j], ref arr[j + 1]);
                }
                Console.WriteLine("排序结果:" + string.Join(",", arr));
                Console.WriteLine($"第{i}次循环结束");
            }
            Console.WriteLine(string.Format("最终排序结果:{0}", string.Join(",", arr)));
            return string.Join(",", arr);
        }

        static void Swap(ref int a, ref int b)
        {
            //int temp = a;
            //a = b;
            //b = temp;
            //元组交换
            (b, a) = (a, b);
        }
    }
}
